package com.eric.similarity.cluster;

import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;

/**
 * 遍历存放相似度的Map，将相似的条目存放到一起
 * 
 * @param 
 *            
 * @return 
 */
public class MapClusterer<K,V> {
	
	public static void main(String[] args) throws IOException {
		HashMap<String,String> list = new HashMap<String,String>();
		
		list.put("a","b");
		list.put("b","c");
		list.put("y","x");
		list.put("c","d");
		list.put("e","f");
		list.put("f","g");
		
		MapClusterer<String,String> c = new MapClusterer<String,String>(); 
		System.out.println(c.Cluster(list));
	}
	
	@SuppressWarnings({ "unchecked" })
	public HashMap<K,List<V>> Cluster (HashMap<K,V> input) {
		K key;
		V value;
		HashMap<K,List<V>> output = new HashMap<K,List<V>>();
		List<String> list = new ArrayList<String>();
		Iterator<Entry<K, V>> it = input.entrySet().iterator();
		
		while (it.hasNext()) {
			Entry<K, V> entry = it.next();
			key = entry.getKey();
			value = entry.getValue();
		
			list.add((String) value);
			
			while (input.get(value) != null) {
				value = input.get(value);
				list.add(new String((String) value));
			}

			output.put((K) key, (List<V>) new ArrayList<String>(list));
			list.clear();
		}
		
		HashMap<K,List<V>> outputTrim = new HashMap<K,List<V>>();
		Iterator<Entry<K, List<V>>> it2 = output.entrySet().iterator();
		while (it2.hasNext()) {
			Entry<K, List<V>> entry = it2.next();
			if (!CheckKeyInMapValue(entry.getKey(),output)) outputTrim.put(entry.getKey(), entry.getValue());
		}
		
		return outputTrim;
	}
	
	@SuppressWarnings({ "unchecked" })
	public boolean CheckKeyInMapValue (K key,HashMap<K,List<V>> input) {
		List<String> value;
		Iterator<Entry<K, List<V>>> it = input.entrySet().iterator();
		
		while (it.hasNext()) {
			Entry<K, List<V>> entry = it.next();

			value = (List<String>) entry.getValue(); 
			if (value.contains(key)) return true;
		}
		return false;
	}
}
